import java.util.LinkedList;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;

public class Solution2583 {

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }

    class LevelTreeNode {
        TreeNode treeNode;
        int level;

        public LevelTreeNode(TreeNode treeNode, int level) {
            this.treeNode = treeNode;
            this.level = level;
        }

        public TreeNode getTreeNode() {
            return treeNode;
        }

        public void setTreeNode(TreeNode treeNode) {
            this.treeNode = treeNode;
        }

        public int getLevel() {
            return level;
        }

        public void setLevel(int level) {
            this.level = level;
        }
    }

    public long kthLargestLevelSum(TreeNode root, int k) {
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> {
            if(a[1] == b[1]){
                return 0;
            } else if(a[1] > b[1]){
                return -1;
            } return 1;
        }
        );
        Queue<LevelTreeNode> levelTreeNodeQueue = new LinkedList<>();
        levelTreeNodeQueue.add(new LevelTreeNode(root, 0));
        long tmpLevel = 0, tmpLevelSum = 0;
        while(!levelTreeNodeQueue.isEmpty()){
            LevelTreeNode levelTreeNode = levelTreeNodeQueue.poll();
            TreeNode node = levelTreeNode.getTreeNode();
            int level = levelTreeNode.getLevel();
            if(Objects.isNull(node)){
                continue;
            }
            if(level > tmpLevel){
                pq.add(new long[]{tmpLevel, tmpLevelSum});
                tmpLevel = level;
                tmpLevelSum = 0;
            }
            tmpLevelSum += node.val;
            levelTreeNodeQueue.add(new LevelTreeNode(node.left, level + 1));
            levelTreeNodeQueue.add(new LevelTreeNode(node.right, level + 1));
        }
        pq.add(new long[]{tmpLevel, tmpLevelSum});

        for (int i = 1; i <= k && !pq.isEmpty(); i++) {
            long res = pq.poll()[1];
            if(i == k){
                return res;
            }
        }
        return -1;
    }
}
